package com.example.leetcode.labuladong.array.prefixsum;

class NumMatrix {
    // preSum[i][j] 记录矩阵 [0, 0, i, j] 的元素和
    private int[][] preSum;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        if (m == 0 || n == 0) return;
        // 构造前缀和矩阵
        preSum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 计算每个矩阵 [0, 0, i, j] 的元素和
                //      0   1   2   3   4   5
                //  0 | 0 | 0 | 0 | 0 | 0 | 0 |
                //  1 | 0 | 3 | 0 | 1 | 4 | 2 |
                //  2 | 0 | 6 | 6 | 3 | 2 | 1 |
                //  3 | 0 | 1 | 2 | 0 | 1 | 5 |
                //  4 | 0 | 4 | 1 | 0 | 1 | 7 |
                //  5 | 0 | 1 | 0 | 3 | 0 | 5 |

                // 如果此时遍历到 i = 4, j = 4, 那么就相当于，计算 3,4 的和 + 4,3 的和 + 当前4,4的值 - 3,3的和

                //      0   1   2   3   4   5
                //      -   -   -   -
                //  0 | 0   0   0   0 | 0 | 0 |
                //  1 | 0   3   0   1 | 4 | 2 |
                //  2 | 0   6   6   3 | 2 | 1 |
                //  3 | 0   1   2   0 | 1 | 5 |
                //  4 | 0 | 4 | 1 | 0 | 1 | 7 |
                //      -   -   -   -
                //  5 | 0 | 1 | 0 | 3 | 0 | 5 |
                //

                preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + matrix[i
                        - 1][j - 1] - preSum[i - 1][j - 1];
            }
        }
    }

    // 计算子矩阵 [x1, y1, x2, y2] 的元素和
    public int sumRegion(int x1, int y1, int x2, int y2) {
        // 目标矩阵之和由四个相邻矩阵运算获得
        return preSum[x2 + 1][y2 + 1] - preSum[x1][y2 + 1] - preSum[x2 + 1][y1] +
                preSum[x1][y1];
    }

    public static void main(String[] args) {
        int[][] ints = {{3, 0, 1, 4, 2}, {5, 6, 3, 2, 1}, {1, 2, 0, 1, 5}, {4, 1, 0, 1, 7}, {1, 0, 3, 0, 5}};
        NumMatrix numMatrix = new NumMatrix(ints);

    }
}